﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Sol437
{
    public int PathSum(TreeNode root, long targetSum)
    {


        if (root == null) return 0;

        int res = RootSum(root, targetSum);




        res += PathSum(root.right, targetSum);
        res += PathSum(root.left, targetSum);


        return res;
    }
    public int RootSum(TreeNode root, long targetSum)//这个遍历所有根节点出发的路径
    {
        int res = 0;
        if (root == null) return 0;
        if (targetSum == root.val)
        {
            res = res + 1;
        }

        res += RootSum(root.left, targetSum - root.val);
        res += RootSum(root.right, targetSum - root.val);

        return res;
    }
}



class Program437
{
    static void Main437(string[] args)
    {
        string preOrder = "10 5 3 3 -2 2 1 -3 11";
        string[] chars = preOrder.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 3, 3, -2, 5, 2, 1, 10, -3, 11 };

        Solution105 solution = new Solution105();



        TreeNode root = solution.BuildTree(nums, inOrder);
        
        Sol437 sol= new Sol437();
       int res= sol.PathSum(root,8);
        Console.WriteLine(  res);


    }
}